package io.zouyalong.algo.leetcode;

/**
 * https://leetcode-cn.com/problems/regular-expression-matching/
 */
public class RegularExpressionMatching {
    public static void main(String[] args) {
        var inst = new RegularExpressionMatching();
        var target = "";
        var pattern = "c*c*";
        System.out.printf("target: %s\n", target);
        System.out.printf("pattern: %s\n", pattern);
        System.out.printf("Matched: %s\n", inst.solution1DP(target, pattern));
    }

    private boolean charMatch(char target, char pattern) {
        return target == pattern || pattern == '.';
    }

    /*
    * 动态规划，从后往前匹配
    * */
    public boolean solution1DP(String s, String p) {
        var sArray = s.toCharArray();
        var pArray = p.toCharArray();
        if (sArray.length == 0 && pArray.length ==0) {
            return true;
        }
        if (pArray.length == 0) {
            return false;
        }
        // match[i][j] 表示 sArray[i] 开始的后子串 和 pArray[j] 开始的后子串是否匹配
        boolean[][] match = new boolean[sArray.length+1][pArray.length+1];
        // 大家都为空串时一定匹配
        match[sArray.length][pArray.length] = true;
        for (int j = pArray.length-1; j >= 1; j-=2) {
            if (pArray[j] == '*') {
                match[sArray.length][j-1] = true;
            } else {
                break;
            }
        }
        for (int j = pArray.length - 1; j >= 0; j--) {
            // 不考虑匹配串错误的情况
            if (pArray[j] == '*') {
                continue;
            }
            for (int i = sArray.length - 1; i >= 0; i--) {
                if (j < pArray.length - 1 && pArray[j+1] == '*') {
                    if (match[i][j+2]) {
                        // 加不加当前的 .* 都能匹配
                        match[i][j] = true;
                        continue;
                    }
                    // 当前 sArray[i] 匹配到 .* 中
                    var matched  = match[i+1][j] && charMatch(sArray[i], pArray[j]);
                    matched = matched || (match[i+1][j+2] && charMatch(sArray[i], pArray[j]));
                    match[i][j] = matched;
                } else {
                    match[i][j] = match[i+1][j+1] && charMatch(sArray[i], pArray[j]);
                }
            }
        }
        return match[0][0];
    }
}
